package main

/*
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
*/
func main() {
	nums := []int{1, 2, 1, 3, 5, 6, 4}
	println(findPeakElement(nums))
}

/**
 *	findPeakElement
 *	@Description: 爬坡法
 *	@param nums []int
 *	@return peak int
 */
/*func findPeakElement(nums []int) (peak int) {
	n := len(nums)
	peak = 0
	for i := 1; i < n; i++ {
		if i == n-1 {
			if nums[n-1] > nums[n-2] {
				return n - 1
			}
			break
		}
		if nums[i] > nums[i-1] && nums[i] > nums[i+1] {
			peak = i
			return peak
		}
	}
	return peak
}*/

func findPeakElement(nums []int) (peak int) {
	left := 0
	right := len(nums) - 1
	return binarySearch(nums, left, right)
}

/**
 *	binarySearch
 *	@Description: 二分查找
 *	@param nums []int
 *	@param left int
 *	@param right int
 *	@return peak int
 */
func binarySearch(nums []int, left, right int) (peak int) {
	if right-left == 0 || right-left == 1 {
		if right-left == 0 {
			return 0
		} else if right-left == 1 {
			if nums[left] > nums[right] {
				return left
			}
			return right
		} else {
			return -1
		}
	}

	mid := (left + right) >> 1

	if nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] {
		return mid
	} else if nums[mid] <= nums[mid-1] {
		return binarySearch(nums, left, mid)
	} else if nums[mid] <= nums[mid+1] {
		return binarySearch(nums, mid, right)
	}
	return -1
}
